FIG. 1 illustrates a typical wireless telecommunications system. Switching center 201 is connected to a plurality of base stations, such as those depicted by base stations 203-1 through 203-5. Additionally, switching center 201 is connected to local or long-distance telephone offices (not shown). Wireless terminals, such as those depicted by terminals 201-1 through 201-3, communicate with a base station which is located in the same pre-determined geographic area, or cell, as itself. For instance, wireless terminals 201-1 and 201-2 are located in cell A, therefore communicate with base station 203-1, which is located in and services cell A.
In order for wireless terminal 201-1 to communicate, it sends a signal via radio waves to base station 203-1; base station 203-1 relays the received signal to switching center 201; and, switching center 201, according to instructions supplied as part of the signal, relays the signal elsewhere. If the desired destination of the signal is another wireless terminal, then switching center 201 relays the signal to a base station located in the same cell as the wireless terminal intended to receive the signal, and the base station transmits the signal via radio waves to the wireless terminal. Likewise, if the desired destination of the signal is a wireline terminal, such as wireline terminal 207, then switching center 201 relays the signal to the desired destination via wirelines to the local or long-distance networks.
When information is transmitted via a digital wireless telecommunications channel, errors can occur in the transmission due to noise, interference and distortion. Various methods are utilized in order to detect and correct errors that occur during transmission. FIG. 2 illustrates some of the components which are typically employed by a digital wireless telecommunications channel in order to detect and correct transmission errors. Information source 12 sends a digital message to encoder 14. The digital message can consist of digitized voice signals, data, etc. Encoder 14 encodes the digital message and feeds it to transmitter 16, which modulates the encoded message onto a carrier and transmits it via radio waves to receiver 18. Receiver 18 receives the message, which may or may not have been corrupted during transmission. Receiver 18 demodulates the received message and feeds it to decoder 20. Decoder 20 decodes the received message and feeds it to information destination 22. Preferably, the digital message fed to information destination 22 is identical to the original digital message which was sent by information source 12.
In order for information destination 22 to receive the same message that was sent by information source 12, encoder 14 and decoder 20 operate to detect and correct errors due to corruption during transmission. Generally, encoder 14 partitions the digital message signal into fixed-length blocks and replaces each block with a codeword uniquely associated with it. The codeword is transmitted instead of the fixed-length block, and the received message is compared to a known set of legitimate codewords in order to determine whether it was corrupted during transmission. One such error detection/correction scheme involves the generation and transmission of Walsh codes.
According to the Walsh code system, encoder 14 partitions a message from information source 12 into blocks having n bits each. Each of the original n-bit blocks of information to be transmitted is converted into a codeword, unique to the block of information, having 2" Walsh chips. Thus, a 3-bit block of data would have a Walsh codeword with 2.sup.3, or 8, Walsh chips. Instead of modulating and transmitting the original 3-bit block of data, transmitter 16 modulates and transmits the Walsh codeword to receiver 18. When the Walsh codeword is received by receiver 18, it is demodulated and fed to decoder 20. Decoder 20 compares the received Walsh codeword, which has potentially been corrupted during transmission, to a set of legitimate Walsh codewords. If the received Walsh codeword matches one of the codewords in the set of legitimate Walsh codewords, then it is presumed that the received codeword was not corrupted during transmission, and can be decoded back into the 3-bit block of information which was originally intended to be transmitted.
If, however, the received Walsh codeword does not match one of the codewords in the set of legitimate Walsh codewords, then the received codeword was corrupted during transmission, and the receiver must determine which of the legitimate Walsh codewords was originally transmitted. In the prior art, a Fast Hadamard Transform (hereinafter "FHT") algorithm is used to calculate, for each received codeword, the likelihood that a received codeword is a particular legitimate Walsh codeword. The FHT algorithm expresses this likelihood as a correlation coefficient. Thus, a received codeword has 2.sup.n correlation coefficients associated with it, one corresponding to each of the 2.sup.n legitimate Walsh codewords. The legitimate Walsh codeword having the largest correlation coefficient is the legitimate codeword most likely to have been transmitted. Thus, the FHT algorithm assigns to a received codeword the legitimate Walsh codeword having the largest correlation coefficient. The "winning" Walsh codeword is then decoded back into a 3-bit block of information and fed to information destination 206.
Although many techniques for implementing Fast Hadamard Transforms are well-known in the prior art, these techniques are generally too slow and require too much hardware.
Thus, there exists a need for an FHT engine that is fast, compact and efficient.